#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <stdbool.h>

typedef struct Node {
    char data;
    struct Node *next;
} Node;

bool has_loop(Node *head)
{
    bool ret = false;
    Node *slow = head;
    Node *fast = head;
    while (slow != NULL && fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast)
        {
            ret = true;
            break;
        }
    }
    return ret;
}

Node *get_nth_node(Node *list, size_t n)
{
    if (n == 1)
    {
        return list;
    }
    else
    {
        return get_nth_node(list->next, n-1);
    }
}

Node *get_tail(Node *list)
{
    if (list == NULL)
    {
        return NULL;
    }
    else
    {
        if (list->next == NULL)
        {
            return list;
        }
        else
        {
            return get_tail(list->next);
        }
    }
}

void print_list(Node * node)
{
    if (node != NULL)
    {
        printf("%c", node->data);
        if (node->next != NULL)
        {
            printf("->");
            print_list(node->next);
        }
        else
        {
            printf("\n");
        }
    }
}

Node *add_node(Node **list, Node *node)
{
    if (*list == NULL)
    {
        *list = node;
    }
    else
    {
        add_node(&(*list)->next, node);
    }
    return *list;
}

Node * new_node(char c)
{
    Node *node = calloc(1, sizeof(Node));
    node->data = c;
    return node;
}

void print_count(Node *list)
{
    int i = 1;
    while (list != NULL)
    {
        printf("[%c(%d)] ", list->data, i);
        list=list->next;
        i++;
    }
}

Node * list_init_from_stdin(void)
{
    Node *list = NULL;
    int c = getchar();
    while (c != EOF)
    {
        if (isgraph(c))
        {
            add_node(&list, new_node(c));
        }
        c = getchar();
    }

    rewind(stdin);

    return list;
}

void release_list(Node *node)
{
    if (node == NULL)
    {
        return;
    }
    if (node->next != NULL)
    {
        release_list(node->next);
    }

    free(node);
}

void detect_loop(Node *list)
{
    printf("\nhas %sloop in list\n", has_loop(list) ? "":"no ");
}

int main(int argc, const char *argv[])
{
    printf("input some characters to init a list. ( EOF (ctr + z) on windows or (ctr + d) on *nix) to finish input)\n");

    Node *list = list_init_from_stdin();

    printf("\n");
    print_list(list);

    detect_loop(list);

    printf("\npick one number to make a loop.\n");
    print_count(list);
    printf("\n");

    // make a loop
    int nth = 0;
    scanf("%d", &nth);
    Node *node_n = get_nth_node(list, nth);
    Node *tail = get_tail(list);

    tail->next = node_n;

    detect_loop(list);

    return 0;
}
